home *** CD-ROM | disk | FTP | other *** search
/ Workbench Design / WB Collection.iso / workbench werkzeuge / scherz programme / fortune / source / ftext.c next >
C/C++ Source or Header  |  1996-04-07  |  5KB  |  328 lines
  1. /*  Source Control
  2. $RCS
  3.  
  4. $version 0.1
  5.  
  6. $date Thu Jun 27 16:13:44 1991
  7.  
  8. $changes :
  9.  
  10. Revision 0.1    Jim Thu Jun 27 16:13:44 1991
  11. compression code copied from Alexa, text handlers moved from support.c
  12.  
  13. Revision 0.0    Jim Thu Jun 27 16:13:33 1991
  14. Added to RCS
  15.  
  16. */
  17.  
  18. /*
  19.  * text handling routines. Modified for fortune!
  20.  */
  21.  
  22. #include <exec/types.h>
  23. #include <stdio.h>
  24. #include <stdlib.h>
  25. #include <ctype.h>
  26. #include <libraries/dos.h>
  27. #include <proto/all.h>
  28.  
  29. static int Oct=0;
  30. static int ONibct=0;
  31. static int Ct=0;
  32. static int Nibct=0;
  33.  
  34. static UBYTE Hoffstr[8000];
  35.  
  36. #define    MSGLISTNUM    31
  37. #define    MAX_TEXT_SIZE    4000
  38.  
  39. /*
  40.  * Huffman code compression routines
  41.  * ---------------------------------
  42.  *
  43.  *     The compression used is a simple adaptive huffman code. Firstly,
  44.  * the text must be analysed. The algorithm is:
  45.  *
  46.  * clearhuffman()            -- clear the character frequency table
  47.  * for each text do
  48.  *         addtohuffman(text)    -- increment the counts for the chars that
  49.  *                             -- appear in this string
  50.  * end
  51.  * genhuffman()                -- sort the frequency table and generate the
  52.  *                             -- huffman compression table.
  53.  * freehuffman()            -- free the frequency table.
  54.  *
  55.  *    The next step is to save the huffman compression table. Assuming a file
  56.  * has been opened, you can do this with savehuffman(filepointer).
  57.  *
  58.  *     Then compress your text. For each text, compress(charptr) returns
  59.  * a character pointer to a text compressed using the current table,
  60.  * generated by the above code.
  61.  *
  62.  *     To decompress a text, you open the file and do loadhuffman(fileptr).
  63.  * This reads the appropriate compression table into memory. Then read the
  64.  * string from the file, and call uncompress(charptr) to get a pointer to
  65.  * the uncompressed string.
  66.  *
  67.  */
  68.  
  69. static UBYTE Hoffarr[20][16];    /* 20 just in case */
  70.  
  71. /* Add a nybble to a string */
  72. static void puthoff(UBYTE n)
  73. {
  74.     if(Nibct==0)
  75.     {
  76.         Hoffstr[Ct]=0;
  77.         Hoffstr[Ct] |= n<<4;
  78.         Nibct++;
  79.     }
  80.     else
  81.     {
  82.         Hoffstr[Ct] |= n&0x0f;
  83.         Nibct=0;
  84.         Ct++;
  85.     }
  86. }
  87.  
  88.  
  89. static int getarray(UBYTE *a,UBYTE *p,UBYTE c)
  90. {
  91.     register UBYTE i,j;
  92.  
  93.     if(!c)
  94.     {
  95.         *a=0;
  96.         *p=0;
  97.         return(1);
  98.     }
  99.     for(i=0;i<20;i++)
  100.         for(j=2;j<16;j++)
  101.         {
  102.             if(Hoffarr[i][j]==c)
  103.             {
  104.                 *a=i;
  105.                 *p=j;
  106.                 return(0);
  107.             }
  108.         }
  109.     printf("Compression error: Character not found in tables- %c(%x)\n",
  110.     c,c);
  111.     exit(0);
  112. }
  113.  
  114. /* get a nybble from a string */
  115. static UBYTE gethoff(UBYTE *a)
  116. {
  117.     register UBYTE q;
  118.     if(ONibct==0)
  119.     {
  120.         ONibct++;
  121.         q=(a[Oct]&0xf0)>>4;
  122.     }
  123.     else
  124.     {
  125.         ONibct=0;
  126.         q=a[Oct++]&0x0f;
  127.     }
  128.     return(q);
  129. }
  130.  
  131.  
  132. /*
  133.  * Compress a null-terminated string down to another null-terminated string
  134.  * using an adaptive huffman code. The table must be initialised, usually
  135.  * with addtohuffman and genhuffman.
  136.  *
  137.  */
  138.  
  139. UBYTE *compress(UBYTE *a)
  140. {
  141.     register int i;
  142.     UBYTE ar,pos,end;
  143.     Ct=0; Nibct=0;
  144.  
  145.     for(i=0;;i++)
  146.     {
  147.         /* What array is the letter a[i] in? */
  148.         end=getarray(&ar,&pos,a[i]);
  149.  
  150.         /* output the appropriate number of zeroes */
  151.  
  152.         for(;ar>0;ar--)
  153.         {
  154.             puthoff(1);
  155.         }
  156.  
  157.         /* output the position */
  158.  
  159.         puthoff(pos);
  160.         if(end)break;
  161.     }
  162.     puthoff(0);
  163.     puthoff(0);
  164.     return(Hoffstr);
  165. }
  166.  
  167. /*
  168.  * Decompress a string. The table must be initialised, usually with
  169.  * loadhuffman() in this case.
  170.  *
  171.  */
  172.  
  173. UBYTE *uncompress(UBYTE *a)
  174. {
  175.     int i,ct=0;
  176.     UBYTE ar,pos;
  177.  
  178.     Oct=0; ONibct=0;
  179.  
  180.     for(i=0;;i++)
  181.     {
  182.         ar=0;
  183.         while((pos=gethoff(a))==1) ar++;
  184.         if(pos==0)break;
  185.         Hoffstr[ct++]=Hoffarr[ar][pos];
  186.         if(ct>1998)
  187.         {
  188.             printf("Error in text docompression - too long!\n");
  189.             exit(0);
  190.         }
  191.     }
  192.     Hoffstr[ct]=NULL;
  193.     return(Hoffstr);
  194. }
  195.  
  196.  
  197. /*
  198.  * Routines for ADAPTIVE huffman coding
  199.  *
  200.  */
  201.  
  202. struct charcnt
  203. {
  204.     UBYTE c;
  205.     long n;
  206. };
  207. static struct charcnt *CharCounts=NULL;
  208.  
  209. /*
  210.  * clear character counts
  211.  *
  212.  */
  213. void clearhuffman(void)
  214. {
  215.     int i;
  216.  
  217.     if(!CharCounts)CharCounts=(struct charcnt *)
  218.         malloc(256*sizeof(struct charcnt));
  219.  
  220.     for(i=0;i<256;i++){CharCounts[i].n=0; CharCounts[i].c=i;};
  221. }
  222.  
  223. void freehuffman(void)
  224. {
  225.     free(CharCounts); CharCounts=NULL;
  226. }
  227.  
  228. /*
  229.  * process ready for coding
  230.  *
  231.  */
  232.  
  233. void addtohuffman(UBYTE *s)
  234. {
  235.     while(*s)CharCounts[*(s++)].n++;
  236. }
  237.  
  238. /*
  239.  * and generate the tables
  240.  *
  241.  */
  242.  
  243. static int compare(struct charcnt *a,struct charcnt *b)
  244. {
  245.     return(b->n - a->n);
  246. }
  247.  
  248. void genhuffman(void)
  249. {
  250.     int tabl=0,slot=2,i;
  251.  
  252.     /* sort the table */
  253.     /* This is the lattice QuickSort function. It sorts an array:
  254.         The format is -
  255.         qsort(pointer to table,    number of elements,
  256.             size of each element, pointer to comparison function)
  257.  
  258.         One problem is that is takes a lot of stack. You'll have to increase
  259.         your stack size quite a lot with the AmigaDOS 'stack' command.
  260.     */
  261.  
  262.     qsort((UBYTE *)CharCounts,256,sizeof(struct charcnt),&compare);
  263.  
  264.     for(i=0;;i++)
  265.     {
  266.         if(!CharCounts[i].n)break;
  267.         Hoffarr[tabl][slot]=CharCounts[i].c;
  268.         if(++slot>15){tabl++,slot=2;};
  269.         if(tabl>19)exit(0);
  270.     }
  271. }
  272.  
  273. /*
  274.  * Save and load huffman tables
  275.  *
  276.  */
  277.  
  278. void savehuffman(BPTR a)
  279. {
  280.     Write(a,&Hoffarr,sizeof(Hoffarr));
  281. }
  282.  
  283. void loadhuffman(BPTR a)
  284. {
  285.     Read(a,&Hoffarr,sizeof(Hoffarr));
  286. }
  287.  
  288. int readshort(BPTR a)
  289. {
  290.     short n;
  291.     int m;
  292.     Read(a,&n,sizeof(short));
  293.     m=(int)n;
  294.     return(m);
  295. }
  296.  
  297. long readlong(BPTR a)
  298. {
  299.     long n;
  300.     Read(a,&n,sizeof(long));
  301.     return(n);
  302. }
  303.  
  304. void writelong(BPTR a,long n)
  305. {
  306.     Write(a,&n,sizeof(long));
  307. }
  308.  
  309. void writeshort(BPTR a,int n)
  310. {
  311.     short m;
  312.  
  313.     m=(short)n;
  314.     Write(a,&m,sizeof(short));
  315. }
  316.  
  317. UBYTE *readstring(UBYTE *buf,int len,BPTR a)
  318. {
  319.     int n,i;
  320.     for(i=0;i<len;i++)
  321.     {
  322.         n=Read(a,buf+i,1);
  323.         if(!n||(buf[i]==NULL))break;
  324.     }
  325.     return(!n?NULL:buf);
  326. }
  327.  
  328.